Search Results

Documents authored by Minato, Shin-ichi

Found 2 Possible Name Variants:

Minato, Shin-Ichi

Document
DOI: 10.4230/LIPIcs.SEA.2023.11
CompDP: A Framework for Simultaneous Subgraph Counting Under Connectivity Constraints

Authors: Kengo Nakamura, Masaaki Nishino, Norihito Yasuda, and Shin-ichi Minato

Published in: LIPIcs, Volume 265, 21st International Symposium on Experimental Algorithms (SEA 2023)

Abstract
The subgraph counting problem computes the number of subgraphs of a given graph that satisfy some constraints. Among various constraints imposed on a graph, those regarding the connectivity of vertices, such as "these two vertices must be connected," have great importance since they are indispensable for determining various graph substructures, e.g., paths, Steiner trees, and rooted spanning forests. In this view, the subgraph counting problem under connectivity constraints is also important because counting such substructures often corresponds to measuring the importance of a vertex in network infrastructures. However, we must solve the subgraph counting problems multiple times to compute such an importance measure for every vertex. Conventionally, they are solved separately by constructing decision diagrams such as BDD and ZDD for each problem. However, even solving a single subgraph counting is a computationally hard task, preventing us from solving it multiple times in a reasonable time. In this paper, we propose a dynamic programming framework that simultaneously counts subgraphs for every vertex by focusing on similar connectivity constraints. Experimental results show that the proposed method solved multiple subgraph counting problems about 10-20 times faster than the existing approach for many problem settings.
Cite as

Kengo Nakamura, Masaaki Nishino, Norihito Yasuda, and Shin-ichi Minato. CompDP: A Framework for Simultaneous Subgraph Counting Under Connectivity Constraints. In 21st International Symposium on Experimental Algorithms (SEA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 265, pp. 11:1-11:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{nakamura_et_al:LIPIcs.SEA.2023.11,
  author =	{Nakamura, Kengo and Nishino, Masaaki and Yasuda, Norihito and Minato, Shin-ichi},
  title =	{{CompDP: A Framework for Simultaneous Subgraph Counting Under Connectivity Constraints}},
  booktitle =	{21st International Symposium on Experimental Algorithms (SEA 2023)},
  pages =	{11:1--11:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-279-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{265},
  editor =	{Georgiadis, Loukas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2023.11},
  URN =		{urn:nbn:de:0030-drops-183613},
  doi =		{10.4230/LIPIcs.SEA.2023.11},
  annote =	{Keywords: Subgraph counting, Connectivity, Zero-suppressed Binary Decision Diagram}
}
Document
DOI: 10.4230/LIPIcs.FUN.2022.16
Sorting Balls and Water: Equivalence and Computational Complexity

Authors: Takehiro Ito, Jun Kawahara, Shin-ichi Minato, Yota Otachi, Toshiki Saitoh, Akira Suzuki, Ryuhei Uehara, Takeaki Uno, Katsuhisa Yamanaka, and Ryo Yoshinaka

Published in: LIPIcs, Volume 226, 11th International Conference on Fun with Algorithms (FUN 2022)

Abstract
Various forms of sorting problems have been studied over the years. Recently, two kinds of sorting puzzle apps are popularized. In these puzzles, we are given a set of bins filled with colored units, balls or water, and some empty bins. These puzzles allow us to move colored units from a bin to another when the colors involved match in some way or the target bin is empty. The goal of these puzzles is to sort all the color units in order. We investigate computational complexities of these puzzles. We first show that these two puzzles are essentially the same from the viewpoint of solvability. That is, an instance is sortable by ball-moves if and only if it is sortable by water-moves. We also show that every yes-instance has a solution of polynomial length, which implies that these puzzles belong to NP . We then show that these puzzles are NP-complete. For some special cases, we give polynomial-time algorithms. We finally consider the number of empty bins sufficient for making all instances solvable and give non-trivial upper and lower bounds in terms of the number of filled bins and the capacity of bins.
Cite as

Takehiro Ito, Jun Kawahara, Shin-ichi Minato, Yota Otachi, Toshiki Saitoh, Akira Suzuki, Ryuhei Uehara, Takeaki Uno, Katsuhisa Yamanaka, and Ryo Yoshinaka. Sorting Balls and Water: Equivalence and Computational Complexity. In 11th International Conference on Fun with Algorithms (FUN 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 226, pp. 16:1-16:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{ito_et_al:LIPIcs.FUN.2022.16,
  author =	{Ito, Takehiro and Kawahara, Jun and Minato, Shin-ichi and Otachi, Yota and Saitoh, Toshiki and Suzuki, Akira and Uehara, Ryuhei and Uno, Takeaki and Yamanaka, Katsuhisa and Yoshinaka, Ryo},
  title =	{{Sorting Balls and Water: Equivalence and Computational Complexity}},
  booktitle =	{11th International Conference on Fun with Algorithms (FUN 2022)},
  pages =	{16:1--16:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-232-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{226},
  editor =	{Fraigniaud, Pierre and Uno, Yushi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2022.16},
  URN =		{urn:nbn:de:0030-drops-159867},
  doi =		{10.4230/LIPIcs.FUN.2022.16},
  annote =	{Keywords: Ball sort puzzle, recreational mathematics, sorting pairs in bins, water sort puzzle}
}
Document
DOI: 10.4230/LIPIcs.SEA.2020.9
Enumerating All Subgraphs Under Given Constraints Using Zero-Suppressed Sentential Decision Diagrams

Authors: Yu Nakahata, Masaaki Nishino, Jun Kawahara, and Shin-ichi Minato

Published in: LIPIcs, Volume 160, 18th International Symposium on Experimental Algorithms (SEA 2020)

Abstract
Subgraph enumeration is a fundamental task in computer science. Since the number of subgraphs can be large, some enumeration algorithms exploit compressed representations for efficiency. One such representation is the Zero-suppressed Binary Decision Diagram (ZDD). ZDDs can represent the set of subgraphs compactly and support several poly-time queries, such as counting and random sampling. Researchers have proposed efficient algorithms to construct ZDDs representing the set of subgraphs under several constraints, which yield fruitful results in many applications. Recently, Zero-suppressed Sentential Decision Diagrams (ZSDDs) have been proposed as variants of ZDDs. ZSDDs can be smaller than ZDDs when representing the same set of subgraphs. However, efficient algorithms to construct ZSDDs are known only for specific types of subgraphs: matchings and paths. We propose a novel framework to construct ZSDDs representing sets of subgraphs under given constraints. Using our framework, we can construct ZSDDs representing several sets of subgraphs such as matchings, paths, cycles, and spanning trees. We show the bound of sizes of constructed ZSDDs by the branch-width of the input graph, which is smaller than that of ZDDs by the path-width. Experiments show that our methods can construct ZSDDs faster than ZDDs and that the constructed ZSDDs are smaller than ZDDs when representing the same set of subgraphs.
Cite as

Yu Nakahata, Masaaki Nishino, Jun Kawahara, and Shin-ichi Minato. Enumerating All Subgraphs Under Given Constraints Using Zero-Suppressed Sentential Decision Diagrams. In 18th International Symposium on Experimental Algorithms (SEA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 160, pp. 9:1-9:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{nakahata_et_al:LIPIcs.SEA.2020.9,
  author =	{Nakahata, Yu and Nishino, Masaaki and Kawahara, Jun and Minato, Shin-ichi},
  title =	{{Enumerating All Subgraphs Under Given Constraints Using Zero-Suppressed Sentential Decision Diagrams}},
  booktitle =	{18th International Symposium on Experimental Algorithms (SEA 2020)},
  pages =	{9:1--9:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-148-1},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{160},
  editor =	{Faro, Simone and Cantone, Domenico},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2020.9},
  URN =		{urn:nbn:de:0030-drops-120831},
  doi =		{10.4230/LIPIcs.SEA.2020.9},
  annote =	{Keywords: Subgraph, Enumeration, Decision Diagram, Zero-suppressed Sentential Decision Diagram (ZSDD), Top-down construction algorithm}
}
Document
DOI: 10.4230/DagSemRep.229
Computer Aided Design and Test Decision Diagrams - Concepts and Applications (Dagstuhl Seminar 99041)

Authors: Bernd Becker, Christoph Meinel, Shin-Ichi Minato, and Fabio Somenzi

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Abstract
Cite as

Bernd Becker, Christoph Meinel, Shin-Ichi Minato, and Fabio Somenzi. Computer Aided Design and Test Decision Diagrams - Concepts and Applications (Dagstuhl Seminar 99041). Dagstuhl Seminar Report 229, pp. 1-16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (1999)

Copy BibTex To Clipboard

@TechReport{becker_et_al:DagSemRep.229,
  author =	{Becker, Bernd and Meinel, Christoph and Minato, Shin-Ichi and Somenzi, Fabio},
  title =	{{Computer Aided Design and Test Decision Diagrams - Concepts and Applications (Dagstuhl Seminar 99041)}},
  pages =	{1--16},
  ISSN =	{1619-0203},
  year =	{1999},
  type = 	{Dagstuhl Seminar Report},
  number =	{229},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemRep.229},
  URN =		{urn:nbn:de:0030-drops-151155},
  doi =		{10.4230/DagSemRep.229},
}

Minato, Shin-ichi

Document
DOI: 10.4230/LIPIcs.SEA.2023.11
CompDP: A Framework for Simultaneous Subgraph Counting Under Connectivity Constraints

Authors: Kengo Nakamura, Masaaki Nishino, Norihito Yasuda, and Shin-ichi Minato

Published in: LIPIcs, Volume 265, 21st International Symposium on Experimental Algorithms (SEA 2023)

Abstract
The subgraph counting problem computes the number of subgraphs of a given graph that satisfy some constraints. Among various constraints imposed on a graph, those regarding the connectivity of vertices, such as "these two vertices must be connected," have great importance since they are indispensable for determining various graph substructures, e.g., paths, Steiner trees, and rooted spanning forests. In this view, the subgraph counting problem under connectivity constraints is also important because counting such substructures often corresponds to measuring the importance of a vertex in network infrastructures. However, we must solve the subgraph counting problems multiple times to compute such an importance measure for every vertex. Conventionally, they are solved separately by constructing decision diagrams such as BDD and ZDD for each problem. However, even solving a single subgraph counting is a computationally hard task, preventing us from solving it multiple times in a reasonable time. In this paper, we propose a dynamic programming framework that simultaneously counts subgraphs for every vertex by focusing on similar connectivity constraints. Experimental results show that the proposed method solved multiple subgraph counting problems about 10-20 times faster than the existing approach for many problem settings.
Cite as

Kengo Nakamura, Masaaki Nishino, Norihito Yasuda, and Shin-ichi Minato. CompDP: A Framework for Simultaneous Subgraph Counting Under Connectivity Constraints. In 21st International Symposium on Experimental Algorithms (SEA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 265, pp. 11:1-11:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{nakamura_et_al:LIPIcs.SEA.2023.11,
  author =	{Nakamura, Kengo and Nishino, Masaaki and Yasuda, Norihito and Minato, Shin-ichi},
  title =	{{CompDP: A Framework for Simultaneous Subgraph Counting Under Connectivity Constraints}},
  booktitle =	{21st International Symposium on Experimental Algorithms (SEA 2023)},
  pages =	{11:1--11:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-279-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{265},
  editor =	{Georgiadis, Loukas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2023.11},
  URN =		{urn:nbn:de:0030-drops-183613},
  doi =		{10.4230/LIPIcs.SEA.2023.11},
  annote =	{Keywords: Subgraph counting, Connectivity, Zero-suppressed Binary Decision Diagram}
}
Document
DOI: 10.4230/LIPIcs.FUN.2022.16
Sorting Balls and Water: Equivalence and Computational Complexity

Authors: Takehiro Ito, Jun Kawahara, Shin-ichi Minato, Yota Otachi, Toshiki Saitoh, Akira Suzuki, Ryuhei Uehara, Takeaki Uno, Katsuhisa Yamanaka, and Ryo Yoshinaka

Published in: LIPIcs, Volume 226, 11th International Conference on Fun with Algorithms (FUN 2022)

Abstract
Various forms of sorting problems have been studied over the years. Recently, two kinds of sorting puzzle apps are popularized. In these puzzles, we are given a set of bins filled with colored units, balls or water, and some empty bins. These puzzles allow us to move colored units from a bin to another when the colors involved match in some way or the target bin is empty. The goal of these puzzles is to sort all the color units in order. We investigate computational complexities of these puzzles. We first show that these two puzzles are essentially the same from the viewpoint of solvability. That is, an instance is sortable by ball-moves if and only if it is sortable by water-moves. We also show that every yes-instance has a solution of polynomial length, which implies that these puzzles belong to NP . We then show that these puzzles are NP-complete. For some special cases, we give polynomial-time algorithms. We finally consider the number of empty bins sufficient for making all instances solvable and give non-trivial upper and lower bounds in terms of the number of filled bins and the capacity of bins.
Cite as

Takehiro Ito, Jun Kawahara, Shin-ichi Minato, Yota Otachi, Toshiki Saitoh, Akira Suzuki, Ryuhei Uehara, Takeaki Uno, Katsuhisa Yamanaka, and Ryo Yoshinaka. Sorting Balls and Water: Equivalence and Computational Complexity. In 11th International Conference on Fun with Algorithms (FUN 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 226, pp. 16:1-16:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{ito_et_al:LIPIcs.FUN.2022.16,
  author =	{Ito, Takehiro and Kawahara, Jun and Minato, Shin-ichi and Otachi, Yota and Saitoh, Toshiki and Suzuki, Akira and Uehara, Ryuhei and Uno, Takeaki and Yamanaka, Katsuhisa and Yoshinaka, Ryo},
  title =	{{Sorting Balls and Water: Equivalence and Computational Complexity}},
  booktitle =	{11th International Conference on Fun with Algorithms (FUN 2022)},
  pages =	{16:1--16:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-232-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{226},
  editor =	{Fraigniaud, Pierre and Uno, Yushi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2022.16},
  URN =		{urn:nbn:de:0030-drops-159867},
  doi =		{10.4230/LIPIcs.FUN.2022.16},
  annote =	{Keywords: Ball sort puzzle, recreational mathematics, sorting pairs in bins, water sort puzzle}
}
Document
DOI: 10.4230/LIPIcs.SEA.2020.9
Enumerating All Subgraphs Under Given Constraints Using Zero-Suppressed Sentential Decision Diagrams

Authors: Yu Nakahata, Masaaki Nishino, Jun Kawahara, and Shin-ichi Minato

Published in: LIPIcs, Volume 160, 18th International Symposium on Experimental Algorithms (SEA 2020)

Abstract
Subgraph enumeration is a fundamental task in computer science. Since the number of subgraphs can be large, some enumeration algorithms exploit compressed representations for efficiency. One such representation is the Zero-suppressed Binary Decision Diagram (ZDD). ZDDs can represent the set of subgraphs compactly and support several poly-time queries, such as counting and random sampling. Researchers have proposed efficient algorithms to construct ZDDs representing the set of subgraphs under several constraints, which yield fruitful results in many applications. Recently, Zero-suppressed Sentential Decision Diagrams (ZSDDs) have been proposed as variants of ZDDs. ZSDDs can be smaller than ZDDs when representing the same set of subgraphs. However, efficient algorithms to construct ZSDDs are known only for specific types of subgraphs: matchings and paths. We propose a novel framework to construct ZSDDs representing sets of subgraphs under given constraints. Using our framework, we can construct ZSDDs representing several sets of subgraphs such as matchings, paths, cycles, and spanning trees. We show the bound of sizes of constructed ZSDDs by the branch-width of the input graph, which is smaller than that of ZDDs by the path-width. Experiments show that our methods can construct ZSDDs faster than ZDDs and that the constructed ZSDDs are smaller than ZDDs when representing the same set of subgraphs.
Cite as

Yu Nakahata, Masaaki Nishino, Jun Kawahara, and Shin-ichi Minato. Enumerating All Subgraphs Under Given Constraints Using Zero-Suppressed Sentential Decision Diagrams. In 18th International Symposium on Experimental Algorithms (SEA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 160, pp. 9:1-9:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{nakahata_et_al:LIPIcs.SEA.2020.9,
  author =	{Nakahata, Yu and Nishino, Masaaki and Kawahara, Jun and Minato, Shin-ichi},
  title =	{{Enumerating All Subgraphs Under Given Constraints Using Zero-Suppressed Sentential Decision Diagrams}},
  booktitle =	{18th International Symposium on Experimental Algorithms (SEA 2020)},
  pages =	{9:1--9:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-148-1},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{160},
  editor =	{Faro, Simone and Cantone, Domenico},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2020.9},
  URN =		{urn:nbn:de:0030-drops-120831},
  doi =		{10.4230/LIPIcs.SEA.2020.9},
  annote =	{Keywords: Subgraph, Enumeration, Decision Diagram, Zero-suppressed Sentential Decision Diagram (ZSDD), Top-down construction algorithm}
}
Document
DOI: 10.4230/DagSemRep.229
Computer Aided Design and Test Decision Diagrams - Concepts and Applications (Dagstuhl Seminar 99041)

Authors: Bernd Becker, Christoph Meinel, Shin-Ichi Minato, and Fabio Somenzi

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Abstract
Cite as

Bernd Becker, Christoph Meinel, Shin-Ichi Minato, and Fabio Somenzi. Computer Aided Design and Test Decision Diagrams - Concepts and Applications (Dagstuhl Seminar 99041). Dagstuhl Seminar Report 229, pp. 1-16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (1999)

Copy BibTex To Clipboard

@TechReport{becker_et_al:DagSemRep.229,
  author =	{Becker, Bernd and Meinel, Christoph and Minato, Shin-Ichi and Somenzi, Fabio},
  title =	{{Computer Aided Design and Test Decision Diagrams - Concepts and Applications (Dagstuhl Seminar 99041)}},
  pages =	{1--16},
  ISSN =	{1619-0203},
  year =	{1999},
  type = 	{Dagstuhl Seminar Report},
  number =	{229},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemRep.229},
  URN =		{urn:nbn:de:0030-drops-151155},
  doi =		{10.4230/DagSemRep.229},
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact